/*
 * SkipSearch.cpp
 *
 *  Created on: 31-08-2013
 *      Author: Krzychu
 */

#include "SkipSearch.h"

#include "Config.h"
#include "List.h"

#include <stdio.h>
#include <string.h>

#define ASIZE 255

SkipSearch::SkipSearch()
{

}

SkipSearch::~SkipSearch()
{

}

std::string SkipSearch::getName()
{
	return "Skip Search";
}

searchResult SkipSearch::execute(std::string text, std::string pattern)
{
	searchResult result;
	result.iterationsTaken = 0;

	int textLength = text.length();
	int patternLength = pattern.length();

	const char* textChar = text.c_str();
	const char* patternChar = pattern.c_str();

	List* ptr;
	List** z = new List*[ASIZE];

	/* Preprocessing */

	for (int i = 0; i < ASIZE; i++)
	{
		ptr = new List();
		ptr->element = -1;
		z[i] = ptr;
	}

	for (int i = 0; i < patternLength; ++i)
	{
		ptr = new List();
		ptr->element = i;
		ptr->next = z[pattern[i]];
		z[pattern[i]] = ptr;
	}

	/* Searching */
	for (int j = patternLength - 1; j < textLength; j += patternLength)
	{
		result.iterationsTaken++;
		for (ptr = z[textChar[j]]; ptr->element != ptr->getUndefined(); ptr = ptr->next)
		{
			if (memcmp(patternChar, textChar + j - ptr->element, patternLength) == 0)
			{
				result.positionsFound.push_back(j - ptr->element);
				if (Config::getInstance()->getFindOneOccurence())
				{
					return result;
				}
			}
		}
	}

	return result;
}
